"""
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 
满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
"""

class Solution(object):
    def threeSum(nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        先对列表进行排序之后可以增加过滤条件从而减少运行时间
        内层的while是第三个数从末尾向前遍历一直到找到第一个不大于target的位置或者遇到第二个数
        """
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i>0 and nums[i]==nums[i-1]:
                continue
            m = n-1
            target = -nums[i]
            for j in range(i + 1, n):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                while j < m and nums[j] + nums[m] > target:
                    m -= 1
                if j == m:
                    break
                if nums[j] + nums[m] == target:
                    res.append([nums[i], nums[j], nums[m]])
        return res